//: [Previous](@previous)
/*:
 
 #21 [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/submissions/)
 
 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
 
 Example:
 ```
 Input: 1->2->4, 1->3->4
 Output: 1->1->2->3->4->4
 ```
 
 */
import Foundation

class Solution {
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let dynamicHead = ListNode(-1)
        var temp = dynamicHead
        
        var temp1 = l1
        var temp2 = l2
        
        while temp1 != nil && temp2 != nil {
            let value1 = temp1?.val ?? 0
            let value2 = temp2?.val ?? 0
            
            if value1 > value2 {
                temp.next = temp2
                temp2 = temp2?.next
            } else {
                temp.next = temp1
                temp1 = temp1?.next
            }
            temp = temp.next!
        }
        
        temp.next = temp1 != nil ? temp1 : temp2        
        return dynamicHead.next
    }
}

var node1 = ListNode(1)
node1.next = ListNode(2)
node1.next?.next = ListNode(4)
var node2 = ListNode(1)
node2.next = ListNode(3)
node2.next?.next = ListNode(4)

print("(\(node1)) + (\(node2)) = (\(String(describing: Solution().mergeTwoLists(node1, node2))))")

//: [Next](@next)
